package 简单.数学;

/**
 * 对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，
 * 我们称它为 「完美数」。
 * <p>
 * 给定一个 整数 n， 如果是完美数，返回 true，否则返回 false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/perfect-number
 */
public class 完美数_507 {

    public static void main(String[] args) {

        System.out.println(Math.pow(2, 2 - 1) * (Math.pow(2, 2) - 1));  //6
        System.out.println(Math.pow(2, 3 - 1) * (Math.pow(2, 3) - 1));  //28
        System.out.println(checkPerfectNumber2(33550336));

    }

    /**
     * 1、质数：
     * 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数
     * 叫做质数。
     * 2、因数：
     * 因数是指整数a除以整数b(b≠0) 的商正好是整数而没有余数，人们就说b是a的因数。
     * 3、合数：
     * 合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。
     * 与之相对的是质数，而1既不属于质数也不属于合数。
     * <p>
     * 因数指的是被别的数整除，而合数指的是可以除其他数可以整除的数，一个被动一个主动
     * <p>
     * 12  6  3
     *
     * @param num
     * @return
     */
    public static boolean checkPerfectNumber(int num) {
        int count = 0;
        for (int i = num / 2; i > 0; i--) {  //超过num的一半一定不是因数
            if (num % i == 0) {
                count += i;
                if (count > num) {
                    return false;
                }
            }
        }
        if (count != num) {
            return false;
        }
        return true;
    }

    /**
     * 如果a/b没有余数，那么a/b=c，b和c都是a的因数
     * 细节：
     * 如果b==c，那么只能计算一个，当c开始大于b时，停止
     * ​
     *
     * @param num
     * @return
     */
    public static boolean checkPerfectNumber2(int num) {
        if (num == 1) {
            return false;
        }
        int count = 1;
        for (int i = 2; i <= num / 2; i++) {
            if (num % i == 0) {
                if (num / i < i) {  //如果num是质数的话，会一直循环到num/2
                    break;
                }
                count += i;
                if (num / i != i) {
                    count += num / i;
                }
                if (count > num) {
                    return false;
                }
            }
        }
        if (count != num) {
            return false;
        }
        return true;
    }

    /**
     * 假设b*b==num，b变大那么c会变小，而小于根号sqrt(num)=b的数已经计算
     * 那么只需要计算<=b的数字
     */
    public static boolean checkPerfectNumber3(int num) {
        if (num == 1) {
            return false;
        }
        int count = 1;
        //直接在循环上降至sqrt(num)的复杂度
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                count += i;
                if (num / i != i) {
                    count += num / i;
                }
                if (count > num) {
                    return false;
                }
            }
        }
        if (count != num) {
            return false;
        }
        return true;
    }

    /**
     * 根据欧几里得-欧拉定理，每个偶完全数都可以写成
     * 2^(p-1)*(2^p-1)。
     * 其中p为素数，2^p-1也是素数
     * 由于目前奇完全数还未被发现
     *
     * @param num
     * @return
     */
    public static boolean efficientCheckPerfectNumber3(int num) {
        return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336;
    }

}
